package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.TreeNode;

/**
 * 1
 * / \
 * 2   5
 * / \   \
 * 3   4   6
 * 将其展开为：
 * <p>
 * 1
 * \
 * 2
 * \
 * 3
 * \
 * 4
 * \
 * 5
 * \
 * 6
 */
public class code114_二叉树原地展开为列表 {
    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.create(
                new int[]{
                        1, 2, 5, 3, 4, -1, 6
                }
        );
        new code114_二叉树原地展开为列表().ans(treeNode);
        System.out.println();
    }

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        ans(root);
    }


    public TreeNode ans(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode left = ans(root.left);
        TreeNode right = ans(root.right);
        root.right = left;
        root.left = null;
        left = root;
        while (left.right != null) {
            left = left.right;
        }
        left.right = right;
        return root;
    }
}
